#define _CRT_SECURE_NO_WARNINGS 1

#include"binary.h"

BTNode* BuyNode(BTDatatype x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail\n");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;

}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);

}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);

}

void BinaryTressSize1(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return;
	}
	(*psize)++;
	BinaryTressSize1(root->left, psize);
	BinaryTressSize1(root->right, psize);
}

int BinaryTressSize2(BTNode* root)
{
	return root == NULL ? 0 : BinaryTressSize2(root->left) + BinaryTressSize2(root->right) + 1;
}

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight= BinaryTreeHeight(root->right);
	if (leftHeight > rightHeight)
	{
		return leftHeight + 1;
	}
	else
	{
		return rightHeight + 1;
	}
}

int BinaryTreeKLevel(BTNode* root, int k)
{
	if (root==NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	int leftk = BinaryTreeKLevel(root->left, k - 1);
	int rightk = BinaryTreeKLevel(root->right, k - 1);
	return leftk+rightk;
}

BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* lret = BinaryTreeFind(root->left, x);
	if (lret)
		return lret;
	BTNode* rret = BinaryTreeFind(root->right, x);
	if (rret)
		return rret;

	return NULL;
}

void LevelOrder(BTNode* root)
{
	Queue Q;
	QInit(&Q);

	//第一个结点入队
	if (root)
	{
		QPush(&Q, root);
	}

	//遍历结点
	while (!QEmpty(&Q))
	{
		//队首元素
		BTNode* front = QFront(&Q);

		//队首元素出队
		QPop(&Q);

		//根结点的值
		printf("%d ", front->data);

		//左右孩子入队
		if (front->left)
			QPush(&Q, front->left);
		if (front->right)
			QPush(&Q, front->right);

	}

	QDestroy(&Q);

}

int isFullBinaryTree(BTNode* root)
{
	Queue Q;
	QInit(&Q);
	//第一个结点入队
	if (root)
	{
		QPush(&Q, root);
	}
	else
	{
		return false;
	}

	//遍历结点
	while (!QEmpty(&Q))
	{
		//队首元素
		BTNode* front = QFront(&Q);

		//队首元素出队
		QPop(&Q);
		if (front == NULL)
		{
			break;
		}

		//左右孩子入队
		else
		{
			QPush(&Q, front->left);
			QPush(&Q, front->right);
		}

	}
	//判断
	while (!QEmpty(&Q))
	{
		//队首元素
		BTNode* front = QFront(&Q);

		//队首元素出队
		QPop(&Q);

		//说明空节点是不连续的
		if (front != NULL)
		{
			QDestroy(&Q);
			return false;
		}

	}

	return true;
	QDestroy(&Q);

}

void DestroyBinaryTree(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	DestroyBinaryTree(root->left);
	DestroyBinaryTree(root->right);
	free(root);
}